package Graph.graphWithNoweight.euler;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/20 20:46
 * @Version 1.0
 *
 * 欧拉回路
 */
public class EulerLoop {
    private Graph G;
    public EulerLoop(Graph graph){
        this.G = graph;
    }

    public boolean hasEulerLoop(){
        CC cc = new CC(G);
        //如果图的 联通分量 大于 1 那么一定不是欧拉回路
        if(cc.count()>1){
            return false;
        }

        for(int v=0;v<G.V();v++){
            //欧拉回路的数学性质 是欧拉回路 《==》 每个顶点的度为偶数。
            if(G.degree(v)%2 == 1){
                return false;
            }
        }
        return true;
    }

    public ArrayList<Integer> result(){
        //用 ArrayList 来模拟 结果栈
        ArrayList<Integer> res = new ArrayList<>();
        if(!hasEulerLoop()){
            return res;
        }else {
            //因为 得出欧拉路径要 删边，，所以先拷贝。
            Graph g = (Graph) G.clone();
            Stack<Integer> stack = new Stack<>();
            int curv = 0;
            //注意 虽然这里push 了两次，但是最后在得到结果集的时候，倒数第二个0的那次 pop出最后一个0，这样 stack就是empty了 ，所以不用管它、
            stack.push(curv);
            while (!stack.isEmpty()){
                if(g.degree(curv)!=0){
                    //其实这里入栈
                    stack.push(curv);
                    //因为 ArrayList 默认实现了迭代器，所以iterator().next() 就是通过这个迭代器取第一个元素。
                    int w = g.adj(curv).iterator().next();
                    g.removeEdge(curv,w);
                    curv = w;
                }else {
                    //如果 degree(curv)
                    res.add(curv);
                    // 把当前栈顶元素（也就是curv） 退栈，放到结果集中去，然后把栈顶上一个元素 赋值给curv看看它有没有degree
                    curv = stack.pop();
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Graph g = new Graph("gEuler.txt");
        EulerLoop eulerLoop = new EulerLoop(g);
        System.out.println(eulerLoop.result());
    }
}
